COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	
C00004 00003	.NSECP(Overview)
C00005 00004	.SSEC(Abstract)
C00007 00005	.SSECP(Five-page Summary of the Project)
C00010 00006	. SSSEC(Detour: Analysis of a discovery)
C00014 00007	. SSSEC(What AM does: Syntheses of discoveries)
C00020 00008	. SSSEC(Results)
C00027 00009	.wantmotiv ← 1
C00030 00010	. SSSEC(Conclusions)
C00032 00011	.SSEC(Ways of viewing AM as some common process)
C00034 00012	. SSSEC(AM as Hill-climbing)
C00038 00013	. SSSEC(AM as Heuristic Search)
C00052 00014	. SSSEC(AM as a Mathematician)
C00063 00015	. SKIP TO COLUMN 1 SSSEC(AM as a Book)
C00069 ENDMK
C⊗;
01::≤*∞A"␈3↔K[N+]$4R4):≤Z&A↓ h(4)tzZ⊗J3QαN⊗≤rV5↓Xh(4)u
D4(hR';∪.+⊃1βN{Uβ∂∞qβWNc⊃β¬εkπ∂#Ns∃βSzβ∪Kπ:β∪↔7}sOSK∂#'[∃ε≠?;∂g+O'?w→β≠?∩βg?U`h+W"α%βSFK;-βN{Uβ∂∞qβ;↔6+Iβ.K3⊃β
β7π∂FK;∃β&CπQβ>K31β'∪π]βεcπWON∪3∃βNs≠↔K.s∂↔Mph(4)jiαC?gK∧4(hQ:⊗N_h(4)u~.&Aβ 4(4P1:N≤*
"π↔≠SKπ∨!$4(hR¬βC⊗{∨Kπja↓β∂∞c3↔⊃α↓
ε5∩aβ'Mαβ∪↔O∨∪'↔"β←#'≡A↓β7}#↔3Mαβ?;∃εOC↔∨!↓β?0h+↔3.k↔;S∂∪e↓βnS#↔nS'∂~βK↔O.K∂!R↓β∪↔6+3?CNs≥β;/9β∂?v≠↔CS~↓βW;&+IβSF(4+∨.K∪π;≡)β?→αβ¬↓βfK∨∃ε∪?∪eαβ?→↓εC↔WKO≠S'
αβKW3/→9↓↓α∩7πSF+7πSN≠M	↓εKL4+≡{;O'&+K↔⊃αβπMβ
↓βSgε)β?→αβ';S.c3'∨.sQ↓β⊗+#π[N{I1βv{Q↓βn+K↔3Hh+πMε	↓β≠Ns'O#. 4+C⊗{∪W∂"p4(4U##∃↓εc?∂πbβ#↔W⊗KOS'∨→β∂?nkW;'≡S∃↓π3'¬β∞qβπ∨.s∪¬↓εk↔∂#∞s'O5bβ¬β∨f{π0hS3'O"β?→β&O/Mε3?Iβ&C∃βOO≠S↔5π#=βC/∪≠?Kjβπ;⊃π∪↔πO}sM↓β>Ceβ↔∞≠!βS∂≠-β'_h+C3∂+O'f)9↓α
βO';>c∃βS∂≠-β7N;#Qβ&KK↔∂"αε5β&yβ∪↔6K;∃β
β;↔]ε≠?;∂/βQ1β␈⊂4+Szβ↔cCf{K∃β≡{7∃↓ε3π∂↔"β?→↓ε9β↔FKOS'v9↓β∂}s∂↔C"aβ?IαβS=β/Cπ7'v)↓βO}k∀4+.kC'KN≠π1↓ε#πS¬αβ≠?IαβK↔∨.cπK'&K↔M1ε+S
9α↓↓αK/β↔πS.#3e1αβS#∃αβCK??∪π44W≠↔3↔∨#Mβ≠⊗{5βSF)↓βπ>+;∪¬π##∃β&O-βF[';:βS#∃ε∪↔OQπ≠WCC␈∪S';:βK↔π≡{;M0hSπ;⊃π##↔9ε+c↔∂/#↔MβO!84(hR↔π∂Bβ∂?;≡+CQβO→↓βπrβπ∂SO3∃1β∨#KW∂'+K↔⊃ε[;?←f+∪∨∃αβ7?∪.c∃9↓∧	↓β#.s∪K↔ h+[↔↔I↓↓βNs∂?7εc↔S∃α↓β7?'+3↔Mα↓βπK*↓β';O#'π3gI↓↓βπ∪?['&+⊃1↓αβ↔π∂B↓↓β?v(4+∂␈∪K↔Oε{;∪'v9↓βSzβπ9β.c↔7↔w#πKeαβO↔Qo##↔?⊗+S'
ε≠?;∂/βQ↓#*s≥91π+;'?rI84*&C'Mβπ∪?['&+M↓β
↓β∪↔6K;'S*βWQαβ'77.sO∃↓↔≠Cπ∂*⊃↓β←FK∂!↓∧
5β.;';MαβS<4V+cC3␈∪∃1β?+'∪↔"↓βeε	β∂?↔βWMβ}1↓IUαβ#↔W⊗KOS'~↓βKWf+M9↓∧
5β↔G#↔;∪~β'SLhS/;?>c↔∪∨*βπO*aβW3&K7πS.ce↓β⊗+∪'O≡{[↔KNs≥β#.s∪K↔'→β?→ε≠?77}qβ∂?v≠↔CS_h)#∃v991βw+7↔↔→%βπv!βS#.{K↔7~↓#∃;:q1βWvKGW∃ε3π∂S␈∪'kπ&K?9%ph(4(1:N≤*∞A"6K[∃7ε∨∃α∨+77π↔Iβ?→π##∃απ∪?+↔∨!$4(hRO∂'.sS'O'→β?≠&+9↓β6∂∃β&C∃β∪N3≠'∂.cQ↓β&O-β}1↓β≠␈∪7W3∂#';≥εs?;S⊗K['π`h+K↔≡+πK∂B↓βCK}∪3↔7~↓β←#N≠!↓β∂∪∃βO}c[πf)9↓↓αα'9↓ε;e↓ε;'[↔rβKπv≠!↓β}04+O≡K↔;∂*aβ'QεKMβW∨+π33Jβ↔πON+IβSzβSπ∂↑c∃β¬π≠C↔∂N3'
β>K[↔9πβK?f+5βSF84+&yβCK␈β?O∃αβ';S/∪↔OSNs≥βg/!↓β7∞sπ∨π⊗c∃β;/9βGW/≠S'?w→↓βSzβ';[/≠S'∨∂#∃84T3?I↓ε+cπ7εc∃1↓ε≠?;S⊗OQ↓↓1SO?g3';≤2QβS#*↓α7'∨≠'?;∂∪'↔Mαβπ;⊃∧≠π;;N∪π3LhSCK?⊗c↔5↓π;'S!α↓βS#*↓↓β7␈∪∃↓βNc17∪.3';↔"↓↓βK.O?;Ns≥↓↓π;#'∂B↓β3↔"↓↓βSxh(YSNs[↔;&K;≤YRβ'Q8hP4*SFKMβ#∞c→β?2βS#∃ε∪??-αβ'M↓ε≠?;∂/∪;↔⊃α↓β←'&A↓β∂⊗+πS'6)↓βSF+?Keα↓β≠?⊗kπS'}q↓β'ph+7π&C↔7π&K∂MiεC?]β&y↓βC⊗{C?O*β';S/∪↔OSNs≥β;/9↓β∂}s∂↔C'→βπ;"↓βC3∂+O'f(4+#Oβ?S#/≠↔Mβ≡{;;↔∨#';≥π##↔5r↓αS#*β↔cC/∪'7↔w#π1↓π3↔#'≡c∃β?2β7eβ⊗+O↔π⊗≠ 4+O→↓β¬ε≠?7C/#↔Iβπ∪?∨K∞iβ∂πfc↔⊃↓↓1Jε42Q⊃⊃α&C∃β?⊗K∨';∞a↓β7.;';:β?→β&C'L4Vk;↔7}s'
βFM↓β⊗+↔9β∞∪π;∪}s↔⊃9α↓απMαα↔c?'+MβO&S↔MR↓α%↓λbε4@	βS#∂!↓α$hP∧bεi@¬9↓ h*';O#'π3gI1αεjβ'L4V;'[↔rβS#∃αβ∪↔≠Ns'S'}sM↓β}1↓EE*↓βO'oβ3∃↓π≠↔Q7&C↔?K/#'
β≡{;∂↔π#M↓↓Fc'/∀hQ
∪↔f+S∃	b↓
↔G.3'SJ⊃%9↓αα↔π∂Bβ∂?;≡+CQβO→βK↔π∪↔O↔w#↔⊃↓εK;S↔⊗sπ33JβπMβλh+∪π&	↓βO'∪W∂S/∪∃↓β>KS!↓αβ¬↓β≡{WC3*↓↓β∪␈S↔9↓π≠3?S~↓↓β?∩↓β≠π≡+SM↓α↓#3'↑(4)
&+≠';O#'?9∩a↓
↔F7C3/→	1↓∃;?KSB⊃%9↓αα';'&Kπ33Jaβ7?∨!β≠π≡+SM↓ε{→β7␈≠P4+≡{;∂↔π#M↓β∂∪∃βf;-1ε;⊃↓∧
5βW≡+Mβ¬αβ∂?3f+∂S'}qβ?→α↓IUAεC↔WKO≠S'∂~↓544Wβ3πW≡K3∃π∪W3↔~β?→↓π##W7∩↓55↓ε3?Iβ?+'∪πv≠∃1↓εMβ'"βSK'/→↓βSzβ≠'3b↓β'8hSS#?≡)β3∞s/M9¬≠?7∃εC↔WKO≠S'∂~βπK∃π+O↔⊃π#=βO.c↔∂Qπ;#'∂BβOC↔≡K≠'
ε3π∂↔ h+?→αβ←#'≡AβOC.≠'≠'~β∂?;≡+CQβ&yβ↔cεc?K∃εs↔cQb↓β←#Nc∃β?&C↔KMεK∃β/≠↔⊃β&x4+π∨#Wπ3gIβ≠'v!↓βO}k∃βππβK?C⊗KπS∃εK;≠?⊗kπS'}q↓βπ⊗{WQβ&C∃β∂F{O↔9αβ≠π∂/!84*␈##↔Iπ∪W3↔~↓βCK}kCQαiβS=αβ;?SN≠∃βONkC3∃π∪↔3π&K?;OFKCM↓ε∪↔S←.+9β/v{←84V≠?;∂/βSM1π#=β∪.3';∃αβCK?nKO';:β;↔]αβ∂?;≡+CSMπ#=↓βNs[↔O&K∨πS*aβπ;"↓βS<hS↔OSNkπS∃εC?]βNsS↔K/≠S';:β↔π∂Bβ∂?;≡+CQβO→84(hP19α≥~N⊗
D#↔S?/⊃iαπv3gOO→β?→ε	β∪'≡≠?[↔↔I$4(hR↔≠␈∪∃↓β&KO∂W∨≠';≥αβ#?]αβS=3#Og;&C↔O'V(Y)↓ε	↓β;/9↓βSF+?Keb↓β∂?w≠'∪↔⊂h+KN+≠3eεC?]β&yYS∞sπ3gV(Y)β}s∃1βF{]βSzβ∂?;∨#KW∂"β¬βCfWO'⊗c∃β∂F'9β}04+K.O?;Ns≥β←FK∂!β&+K7'vS↔MεK9β¬ε;'[↔rβ∪'O≡{[↔KJq↓α?v)β∂πrβ∪=↓π##'Mε∪d4+>{K/'v9↓β∞≠/←π⊗#M1↓ε∪eβK.#W∂'v9↓βSF)↓β∂⊗+πS'6)↓βπ∨!βS=αβO'7εc↔I↓ε;⊂4W≠'7Cf+I↓β∨∪↔πSO3∃βπ∨#M9↓αα≠?Iε+cπ7εc∃1β≡{;O'&+IβSF)↓β∂}s∂↔C"β?→βπ∪'7∀hS;W7⊗+KM9αα#?]εk'∨#"↓β?;*β∃βf+⊃βSz↓β∪↔6K;∃β∨+∂!β
β;?SN{9⎇↓∧s?S'≡)βS#(h+≠?fc?←'v9βC3∂+O'f)βOS⊗S↔∨KP4(4Rr>:∞*α&:∩,rQ↓ecI1eα≤*2⊗∞"↓X4(hQ
'→ε1β'Ma function which transforms elements of  A into elements of
B, and B is ordered, then consider just those members of A which  are
transformed  into  ⊗4extremal⊗*  elements of  B.    This  set  is  an
interesting subset of A."

When  f(x) means "divisors  of x", and  the ordering  is "by length",
this heuristic says to consider those numbers which have  a minimal$$
The other extreme, numbers with a MAXIMAL number of factors, was also
proposed  by  AM  as  worth  investigating.    This  led  AM to  many
interesting questions. $ number of factors
-- that is,  the primes.  So this rule  actually ⊗4reduces⊗* our task
from "proposing the concept of prime numbers" to the more  elementary
problems   of   "discovering   ordering-by-length"   and   "inventing
divisors-of".

But  suppose we  know this  general rule: ⊗6"If  f is  an interesting
function, consider its inverse."⊗* It reduces the task of discovering
divisors-of to the simpler  task of discovering multiplication$$ Plus
noticing  that  multiplication  is  associative  and  commutative. $.
Eventually, this task reduces to the discovery of very basic notions,
like substitution,  set-union, and equality.  To  explain how a given
researcher might have  made a  given discovery, such  an analysis  is
continued  until that  inductive  task  is reduced  to  "discovering"
notions which the  researcher already knew, which were his conceptual
primitives.

. SSSEC(What AM does: Syntheses of discoveries)

.QQ

This leads to the paradox that the more original a discovery the more obvious
it seems afterwards.
The creative act is not an act of creation in the sense of the Old Testament.
It does not create something out of nothing; it uncovers, selects, re-shuffles,
combines, synthesizes already existing facts, faculties, skills.
The more familiar the parts, the more striking the new whole.

-- Koestler

.ESS

Suppose a  large collection  of these  heuristic strategies has  been
assembled (e.g.,  by analyzing a great  many discoveries, and writing
down new heuristic rules whenever necessary).  Instead of  using them
to ⊗4explain⊗* how  a given idea might have evolved,  one can imagine
starting from  a basic core of knowledge and "running" the heuristics
to ⊗4generate⊗*  new concepts.    We're talking  about reversing  the
process  described  in  the  last  section: not  how  to  ⊗4explain⊗*
discoveries, but how to ⊗4make⊗* them.

Such syntheses are precisely what AM does.  The program consists of a
large corpus  of  primitive mathematical  concepts, each  with a  few
associated  heuristics$$  Situation/action  rules  which function  as
local "plausible move generators".  Some suggest tasks for the system
to carry out,  some suggest ways of satisfying a  given task, etc. $.
AM's  activities all  serve to  expand AM  itself, to enlarge  upon a
given body of mathematical knowledge.   To cope with the  enormity of
the  potential "search  space" involved,  AM uses  its  heuristics as
judgmental criteria  to  guide  development  in  the  most  promising
direction.  It appears that the process of inventing worthwhile new$$
Typically,  "new" means new to  AM, not to  Mankind; and "worthwhile"
can  only  be  judged  in  hindsight.    $  concepts  can  be  guided
successfully using a collection of a few hundred such heuristics.

Each concept  is represented as  a frame-like data structure  with 25
different facets  or slots.  The types of facets include: ⊗6Examples,
Definitions,      Generalizations,      Domain/Range,      Analogies,
Interestingness,⊗*  and  many  others.    Modular  representation  of
concepts provides a convenient scheme for organizing the  heuristics;
for example, the following strategy fits  into the ⊗4Examples⊗* facet
of  the ⊗4Predicate⊗* concept:  ⊗6"If, empirically, 10  times as many
elements ⊗4fail⊗*  some predicate  P, as  ⊗4satisfy⊗*  it, then  some
⊗4generalization⊗* (weakened version) of  P might be more interesting
than  P"⊗1.   AM considers  this suggestion  after trying to  fill in
examples of  each  predicate$$ In  fact, after  AM  attempts to  find
examples  of  SET-EQUALITY,  so few  are  found  that  AM decides  to
generalize that predicate.  The result is the creation of 
a new predicate which means
"Has-the-same-length-as" -- i.e., a rudimentary  precursor to natural
numbers.  $.

AM is initially  given a collection of 115 core concepts, with only a
few facets filled in for each.   Its sole activity is to choose  some
facet  of some  concept, and  fill in  that particular  slot.   In so
doing,  new  notions  will  often  emerge.    Uninteresting ones  are
forgotten, mildly interesting ones are kept as parts of  one facet of
one   concept,   and  very   interesting   ones   are  granted   full
concept-module status. Each of these new modules has dozens of  blank
slots, hence the space of possible actions  (blank facets to fill in)
grows  rapidly.   The same  heuristics are used  both to  suggest new
directions for investigation, and to limit attention: both  to sprout
and to prune.

. SSSEC(Results)

The particular mathematical domains in which  AM operates depend upon
the  choice of initial concepts.   Currently, AM  begins with nothing
but a scanty  knowledge of  concepts which Piaget  might describe  as
⊗4prenumerical⊗*:  Sets, substitution,  operations, equality,  and so
on.     In  particular,   AM  is  not  told   anything  about  proof,
single-valued functions, or numbers.

From this  primitive basis, AM  quickly discovered$$ "Discovering"  a
concept  means that (1)  AM recognized  it as a  distinguished entity
(e.g., by formulating its definition) and also (2) AM decided it  was
worth investigating  (either because  of the  interesting way it  was
formed,  or because of  surprising preliminary  empirical results). $
elementary numerical concepts (corresponding to those we refer  to as
natural numbers,  multiplication, factors,  and primes)  and wandered
around  in  the  domain  of  elementary  number  theory.    AM was not designed
to ⊗4prove⊗*  anything,  but  it  did  ⊗4conjecture⊗*  many  well-known
relationships (e.g., the unique factorization theorem).

AM was  not able to discover any  "new-to-Mankind" mathematics purely
on its  own,  but  ⊗4has⊗*  discovered  several  interesting  notions
hitherto unknown to the author. A couple bits of new mathematics have
been ⊗4inspired⊗* by AM.⊗A2⊗* A synergetic AM--human combination can
sometimes produce better research than either could alone.$$  This is
supported by Gelernter's experiences with his geometry program: While
lecturing about  how it might prove a certain theorem about isosceles
triangles, he came  up with a new,  cute proof. Similarly, Guard  and
Eastman  noticed  an  intermediate  result  of their  SAM  resolution
theorem prover, and wisely interpreted  it as a nontrivial result  in
lattice theory  (now known as  SAM's lemma). $  Although most  of the
concepts AM  proposed and developed were already  very well known, AM
defined some of them in novel ways (e.g., prime pairs were defined by
restricting addition to primes; that is, for which primes p,q,r is it
possible  that p+q=r?$$ The answer  is that either p or  q must be 2,
and that the other two  primes are a prime pair -- i.e.,  they differ
by two. $).

Everything that AM does can  be viewed as testing the underlying body
of  heuristic  rules.    Gradually,  this  knowledge  becomes  better
organized, its implications clearer.  The  resultant body of detailed
heuristics  may  be  the  germ  of  a  more efficient  programme  for
educating  math students  than  the  current  dogma$$  Currently,  an
educator takes  the very best  work any mathematician has  ever done,
polishes it until its brilliance is blinding, then presents it to the
student to induce upon. Many individuals (e.g., Knuth and Polya) have
pointed  out this  blunder.   A few  (e.g., Papert  at MIT,  Adams at
Stanford)  are  experimenting  with  more  realistic  strategies  for
"teaching" creativity.  See the references by these authors in the bibliography. $.

Another   benefit   of   actually  constructing   AM   is   that   of
⊗4experimentation⊗*: one  can vary the concepts  AM starts with, vary
the  heuristics available,  etc.,  and  study  the  effects  on  AM's
behavior.   Several such  experiments were  performed.   One involved
adding a couple dozen new concepts from an entirely new domain: plane
geometry.  AM busied itself exploring  elementary geometric concepts,
and was  almost as productive there  as in its original  domain.  New
concepts  were  defined,  and  new  conjectures  formulated.    Other
experiments indicated  that AM was  more robust than  anticipated; it
withstood  many  kinds  of  "de-tuning".    Others  demonstrated  the
tremendous impact that  a few  key concepts (e.g.,  Equality) had  on
AM's behavior.   Several  more experiments  and extensions  have been
planned for the future.

.wantmotiv ← 1;
.if wantmotiv=1 then start;
. SSSEC(Motivation)

.QQ

We need a super-mathematics in which the operations are as unknown as
the quantities  they operate on, and  a super-mathematician, who does
not know what he is doing when he performs these operations.

-- Eddington

.ESS


Although the  motivation for  carrying out  this  research of  course
preceded the effort,  I have delayed until this  section a discussion
of why this is worthwhile, why it was attempted.

First  there  was  the  inherent  interest  of  getting  a handle  on
scientific creativity.    AM is  partly  a demonstration  that  some
aspects of  creative theory formation can be  demystified, can be
modelled as simple rule-governed behavior.

Related to this is the potential for learning from AM more about  the
processes of concept  formation. This was touched on  previously, and
several experiments already performed on AM will be detailed later.

Third, AM itself  may grow into something of pragmatic value. Perhaps
it will become a useful tool for mathematicians, for educators, or as
a  model for  similar systems in  more "practical"  fields.   Perhaps in  the
future we  scientists will be able to rely on automated assistants to
carry  out  the "hack"  phases  of  research,  the  tiresome  legwork
necessary for "secondary" creativity.

Historically, the  domain of AM came  from a search  for a scientific
field whose activities  had no  specific goal, and  in which  natural
language abilities were unnecessary.  This was to test out the BEINGs
[Lenat 75b]
ideas for a modular representation of knowledge.

It  would be  unfair not to  mention the  usual bad reasons  for this
research: the  "Look  ma, no  hands"  syndrome, the  AI  researcher's
classic maternal urges, ego, the usual thesis drives, etc.

.end;

. SSSEC(Conclusions)

AM is forced to judge ⊗4a priori⊗* the value  of each new concept, to
lose interest quickly  in concepts which aren't going to develop into
anything.  Often, such judgments can only be based on hindsight.  For
similar reasons,  AM has difficulty formulating  new heuristics which
are  relevant to the new  concepts it creates.   Heuristics are often
merely  compiled  hindsight.   While  AM's  "approach"  to  empirical
research may be used in other scientific domains, the main limitation
(reliance on hindsight) will probably  recur.  This prevents AM  from
progressing indefinitely far on its own.

This ultimate limitation  was reached. AM's performance  degraded more
and  more as  it progressed  further  away from  its initial  base of
concepts.   Nevertheless, AM  demonstrated that  selected aspects  of
creative  discovery in  elementary  mathematics  could be  adequately
represented  as a heuristic search process.   Actually constructing a
computer model of this activity has provided  an experimental vehicle
for studying the dynamics of plausible empirical inference.

.SSEC(Ways of viewing AM as some common process)

This section will provide  a few metaphors: some hints  for squeezing
AM  into paradigms  with which  the  reader might  be familiar.   For
example, the existence of heuristics  in AM is functionally the  same
as the presence of domain-specific information in any knowledge-based
system.

Consider   assumptions,  axioms,  definitions,  and  theorems  to  be
syntactic rules  for the  language that  we call  Mathematics.   Thus
theorem-proving, and  the whole of textbook mathematics,  is a purely
syntactic process.  Then the heuristic rules used by a  mathematician
(and by  AM) would  correspond to  the semantic knowledge  associated
with these more formal methods.

Just   as   one   can   upgrade   natural-language-understanding   by
incorporating semantic  knowledge, so AM is  only as  successful as  the
heuristics it knows.

Four more  ways of "viewing" AM  as something else will  be provided:
(i)  AM as  a hill-climber,  (ii) AM  as a heuristic  search program,
(iii) AM as a mathematician, and (iv) AM as half a book.

. SSSEC(AM as Hill-climbing)

Let's draw an analogy between 
the process of
developing new mathematics and the familiar
process of  hill-climbing.  We may visualize  AM as exploring a space
using a measuring or "evaluation" function which imparts to it a topography.

Consider AM's  core of  very simple  knowledge.   By compounding  its
known concepts  and methods, AM  can explore beyond the frontier of
this foundation  a little
wherever  it  wishes.   The  incredible  variety  of  alternatives to
investigate includes  all known mathematics,  much trivia,  countless
deadends, and so  on.  The only "successful" paths  near the core are
the narrow ridges  of known  mathematics (plus perhaps  a few  
as-yet-undiscovered isolated peaks).

How  can  AM walk  through  this  immense  space, with  any  hope  of
following   the   few,   slender   trails  of   already-established
mathematics (or  some equally  successful new  fields)?   AM must  do
hill-climbing: As new concepts are  formed, decide how promising they
are, and always explore the  currently most-promising new  concept.  The
evaluation function  is quite  nontrivial, and the work reported
in this half of the book may  be
viewed  as  an  attempt  to  study  and  explain  and  duplicate  the
judgmental criteria  people  employ.    Preliminary attempts$$ 
These took the form of informal simulations. Although far from controlled
experiments, they indicated the feasability of attempting to create AM,
by yielding an approximate figure for the amount of informal knowledge
such a system would need.
$ at  codifying  such
"mysterious"  emotive  forces  as   intuition,  aesthetics,  utility,
richness,  interestingness, relevance...  indicated  that a large but
not unmanageable collection of heuristic rules should suffice.

The important visualization  to make is  that with proper  evaluation
criteria, AM's  planar mass  of interrelated concepts  is transformed
into  a  three-dimensional relief  map:  the known  lines  of development
become mountain ranges, soaring above the vast flat  plains of trivia
and inconsistency below.

Occasionally an  isolated hill is  discovered near the  core;$$ E.g.,
Conway's numbers,  as  described  in [Knuth 74]. $
certainly whole  ranges lie undiscovered  for long periods  of time$$
E.g., non-Euclidean geometries weren't thought of until 1848.  $, and
the terrrain far from the initial core is not yet explored at all.

. SSSEC(AM as Heuristic Search)

We earlier referred to AM as a
kind  of  "heuristic search"  program.  That  must mean  that  AM is
exploring  a  particular  "space,"  using  some  informal  evaluation
criteria to guide it.

The flavor  of search  which is  used here  is that  of progressively
enlarging  a tree. Certain  "evaluation-function" heuristics are used
to decide which  node of the tree  to expand next, and  other guiding
rules  are then  used to  produce from  that node  a  few interesting
successor nodes. To do mathematical research well, I claim that it is
necessary  and sufficent  to  have  good  methods for  proposing  new
concepts  from existing ones,  and for deciding  how interesting each
"node" (partially-studied concept) is.

AM is  initially supplied with  a few  facts about  some simple  math
concepts.  AM then explores mathematics by selectively enlarging that
basis.  One  could  say  that  AM  consists  of  an  active  body  of
mathematical concepts, plus enough  "wisdom" to use and  develop them
effectively. For "wisdom", read "heuristics". Loosely speaking, then,
AM is a heuristic search program.  To see this more clearly, we  must
explain what the nodes  of AM's search space are,  what the successor
operators or links are, and what the evaluation function is.

AM's  space  can be  considered to  consist  of all  nodes  which are
consistent, partially-filled-in  concepts.  Then a  primitive  "legal
move" for AM would  be to (i) enlarge some facet  of some concept, or
(ii)  create a new,  partially-complete concept. Consider momentarily
the size of this space.  If there were no constraint  on what the new
concepts  can  be, and  no  informal  knowledge  for quickly  finding
entries for a desired  facet, a blind  "legal-move" program would  go
nowhere --  slowly!   One  shouldn't even  call the  activity such  a
program would be doing "math research."

The heuristic  rules are used as  little "plausible move generators".
They suggest which facet of  which concept to enlarge next, and  they
suggest specific new concepts to create. The only activities which AM
will  consider doing  are those  which have  been motivated  for some
specific good$$ Of  course, AM thinks  a reason is  "good" if --  and
only if --  it was told that by a heuristic  rule; so those rules had
better be  plausible,  preferably  the  ones  actually  used  by  the
experts.   $  reason. A  global ⊗4agenda  of  tasks⊗* is  maintained,
listing all the activities suggested but not yet worked on.

AM has a definite  algorithm for rating the nodes of its space.  Many
heuristics exist merely to estimate  the worth of any given  concept.
Other heuristics  use these worth ratings  to order the tasks  on the
global  agenda list.  Yet AM  has no  specific goal criteria:  it can
never "halt", never succeed or fail in any absolute sense. AM goes on
forever$$  Technically, forever  is about  100,000 list  cells  and a
couple cpu hours. $.

Consider Nilsson's  descriptions of  depth-first  searching   and 
breadth-first searching 
([Nilsson 71]).
He has  us maintain a list of  "open" nodes.
Repeatedly,  he plucks the  top one and  expands it.  In the process,
some new  nodes  may be  added  to the  Open  list.  In the  case  of
depth-first searching,  they are added at  the top; the next  node to
expand is  the one most recently created; the Open-list is being used
as a push-down stack.  For breadth-first search, new  nodes are added
at the  bottom; they aren't expanded  until all the  older nodes have
been; the Open-list  is used as  a queue.   For heuristic search,  or
"best-first" search, new nodes are evaluated in some numeric way, and
then "merged" into the already-sorted list of Open nodes.

.ONCE TURN ON "{}"

This  process is  very similar  to  the agenda  mechanism AM  uses to
manage its  search.  This will  be  discussed  in detail  in  Chapter
{[2]AGENDA}.  Each entry on the agenda consists of three parts: 
(i) a plausible task for AM
to  do, (ii)  a list  of reasons  supporting that  task, and  (iii) a
numeric estimate  of the  overall  priority this  task should  have.
When a task is suggested  for some reason, it is added to the agenda.
A task may be  suggested several times, for  different reasons.   The
global priority value assigned to each task  is based on the combined
value  of its  reasons.   The control  structure of  AM is  simply to
select the task with the  highest priority, execute it, and select  a
new one.  The agenda mechanism  appears to be a very well-suited data
structure for managing a "best-first" search process.

Similar  control structures  were used  in LT 
[Newell, Shaw, & Simon 57], the predictor part of
Dendral
[Buchanan et al 69], SIMULA-67 [Dahl 68], 
and  KRL [Bobrow & Winograd
77].
The main difference is that in AM, symbolic reasons are
used (albeit in trivial token-like ways) to decide whether -- and how
much -- to boost the priority of a task when it is suggested again.

There are several difficulties  and anomalies in forcing AM  into the
heuristic  search paradigm.   
In a typical heuristic search
(e.g., Dendral [Feigenbaum et al 71], Meta-Dendral [Buchanan et al 72],
most game-playing programs [Samuel 67]),
a "search space" is defined implicitly by a
"legal move generator". Heuristics are present to constrain that
generator so that only plausible nodes are produced. 
The second kind of heuristic
search, of which AM is an example, contains no "legal move generator".
Instead, 
AM's heuristics  are used  as plausible
move generators.
Those heuristics themselves implicitly define the possible tasks AM might
consider, and ⊗4all⊗* such tasks should be plausible one. In the first kind of
search, removing a heuristic widens the search space; in AM's kind of
search, removing a heuristic ⊗4reduces⊗* it.

.HSEARCH: PAGE;

Another anomaly is  that the operators which  AM uses to enlarge  and
explore  the space of  concepts are themselves  mathematical concepts
(e.g., some heuristic rules result  in the creation of new  heuristic
rules; "Compose" is both a concept and  an operation which results in
new concepts).  Thus AM should be viewed as a mass of knowledge which
enlarges ⊗4itself⊗*  repeatedly.   Typically, 
computer  programs  keep  the  information  they  "discover"  quite
separate from the knowledge they use to make discoveries$$ Of course
this  is often  because  the  two  kinds of  knowledge  are  very
different:  For  a  chess-player,  the  first  kind  is  "good  board
positions," and the second  is "strategies for  making a good  move."
Theorem-provers are an exception. They produce 
a new theorem, and then use it (almost like a new operator) in future proofs.
A program to learn
to play checkers [Samuel 67] has this same flavor, thereby indicating that
this `self-help' property is not a function of the task
domain, not simply a characteristic of mathematics.  $

Perhaps  the  greatest difference  between AM  and  typical heuristic
search procedures is that AM  has no well-defined target concepts  or
target relationships.   Rather, its "goal criterion" --  its sole aim
--  is to  maximize the  interestingness level  of the  activities it
performs, the priority  ratings of the top  tasks on the agenda.   It
doesn't  matter   precisely  which  definitions   or  conjectures  AM
discovers -- or misses -- so long as it spends its time on  plausible
tasks.  There is no fixed set of theorems that AM should discover, so
AM  is not  a typical  ⊗4problem-solver⊗*. There is  no fixed  set of
traps AM should avoid, 
no small set of legal moves,
and no winning/losing behavior, 
so AM is not a
typical ⊗4game-player⊗*.

For  example,  no stigma  is  attached  to  the  fact that  AM  never
discovered  real  numbers$$ There  are  many "nice"  things  which AM
didn't -- and can't -- do: e.g., devising ↓_geometric_↓ concepts from
its initial  simple set-theoretic knowledge.   See the  discussion of
the limitations of AM, Section {[2]DIFSECNUM}.{[2]DIFSSECNUM}. $;  it
was  rather  surprising  that  AM  managed  to  discover  ⊗4natural⊗*
numbers!    Even   if  it  hadn't  done  that,  it  would  have  been
acceptable$$ Acceptable to whom?  Is there really a  domain-invariant
criterion  for  judging  the  quality  of  AM's  actions?    See  the
discussions in  Section {[2]EVALU}.1. $ if AM had simply gone off and
developed ideas in set theory.

. SSSEC(AM as a Mathematician)

.AMAM: PAGE;

.AMAMSSEC: SSECNUM;

Before diving into the innards of AM, let's  take a moment to discuss
the  totality  of the  mathematics  which  AM carried  out.    Like a
contemporary  historian  summarizing  the  work  of  the   Babylonian
mathematicians, we shan't hesitate to use current terms and criticize
by current standards.

AM   began  its  investigations  with  scanty   knowledge  of  a  few
set-theoretic concepts  (sets,  equality  of sets,  set  operations).
Most  of the obvious  set-theory relations  (e.g., de  Morgan's laws)
were eventually uncovered; since  AM never fully understood  abstract
algebra, the statement  and verification of  each of these  was quite
obscure.    AM never  derived a  formal  notion of  infinity,  but it
naively established conjectures like "a set can never be a  member of
itself", and procedures for making chains  of new sets ("insert a set
into  itself").  No sophisticated  set theory (e.g., diagonalization)
was ever done.

After this initial period of exploration, AM  decided that "equality"
was   worth  generalizing,  and   thereby  discovered   the  relation
"same-size-as".  "Natural numbers" were based on this, and soon  most
simple arithmetic operations were defined.

Since addition arose as  an analog to union, and  multiplication as a
repeated  substitution followed by  a generalized  kind of unioning$$
Take two bags A and B. Replace each element of A by the bag B. Remove
one level of  parentheses by taking the union of  all elements of the
transfigured bag  A.  Then that new bag will have as many elements as
the product of  the lengths of  the two original  bags. $ it came  as
quite  a surprise  when AM  noticed that  they were  related (namely,
N+N=2⊗7x⊗*N).  AM later re-discovered multiplication in three other ways:
as repeated addition, as the numeric analog  of the Cartesian product
of sets, and  by studying the cardinality of power sets$$ The size of
the set of all subsets  of S is 2↑|↑S↑|.   Thus the power set of A∪B  has
length equal to the ↓_product_↓ of the lengths of the power sets of A
and  B  individually  (assuming A  and  B are  disjoint).  $.   These
operations were defined  in different ways,  so it was an  unexpected
(to AM)  discovery when they all  turned out to  be equivalent. These
surprises caused AM to  give the concept `Times'  quite a high  Worth
rating.

Exponentiation was defined as repeated multiplication. Unfortunately,
AM never  found any obvious properties  of exponentiation, hence lost
all interest in it.

Soon after defining  multiplication, AM  investigated the process  of
multiplying a number by itself: squaring.  The inverse of this turned
out to  be interesting, and led to the definition of square-root.  AM
remained   content   to    play   around   with   the    concept   of
⊗4integer⊗*-square-root.  Although  it isolated  the  set of  numbers
which  had  no  square  root,  AM  was  never  close  to  discovering
rationals, let alone irrationals.

Raising to fourth-powers, and fourth-rooting, were discovered at this
time.  Perfect squares and perfect fourth-powers were isolated.  Many
other numeric operations  and kinds of  numbers were isolated:  Odds,
Evens,  Doubling,   Halving,  etc.   Primitive  notions   of  numeric
inequality were defined but AM never even discovered Trichotomy.

.ONCE TURN ON "{}"

The  associativity and commutativity of multiplication indicated that
it could accept a  BAG of numbers as  its argument.  When  AM defined
the inverse  operation corresponding to Times,  this property allowed
the definition to be: "any ⊗4bag⊗*  of numbers (>1) whose product  is
x".     This  was  just   the  notion  of   factoring  a   number  x.
Minimally-factorable  numbers turned out  to be what  we call primes.
Maximally-factorable numbers were also thought to be interesting.

Prime pairs were discovered in a bizarre way: by restricting addition
(its arguments and its values) to Primes.$$ That is, consider the set
of triples  p,q,r, all primes, for which p+q=r. Then one of them must
be "2",  and the other  two must therefore  form a  prime pair. $  AM
conjectured   the   fundamental   theorem   of   arithmetic   (unique
factorization into  primes)  and Goldbach's  conjecture  (every  even
number >2 is the sum of two primes)  in a surprisingly symmetric way.
The unary representation of numbers gave way to a representation as a
bag of primes (based on  unique factorization), but AM never  thought
of  exponential  notation.   
$$ A tangential note:
All of the discoveries mentioned above were made by AM working
by itself, with a human being observing its behavior. If the
level of sophistication of AM's concepts were higher (or the level
of sophistication of its users were lower), then it might be worthwhile
to develop a nice user--system interface. The user in that case
could -- and ought to -- work right along with AM as a co-researcher. $
Since  the  key concepts  of  remainder,
greater-than,  gcd, and exponentiation  were never mastered, progress
in number theory was arrested.

When a new base of ⊗4geometric⊗* concepts was added, AM began finding
some more  general associations.  In place  of the strict definitions
for  the  equality  of  lines,   angles,  and  triangles,  came   new
definitions  of concepts  we  refer  to as  Parallel,  Equal-measure,
Similar,  Congruent, Translation, Rotation,  plus many  which have no
common name (e.g. the relationship of two triangles sharing  a common
angle).  A cute geometric interpretation of Goldbach's conjecture was
found$$   Given   all  angles   of   a  prime   number   of  degrees,
(0,1,2,3,5,7,11,...,179 degrees),  then any angle  between 0 and  180
degrees can be approximated (to within 1 degree) as the sum of two of
those  angles.  $.     Lacking  a   geometry  "model"  (an   analogic
representation like  the one  Gelernter employed),  AM was doomed  to
failure   with  respect   to   proposing  only   plausible  geometric
conjectures.

Similar restrictions due to poor "visualization" abilities would crop
up in  topology.  The  concepts of continuity, infinity,  and measure
would  have to  be fed  to AM  before it  could enter the  domains of
analysis. More and more drastic changes in its initial  base would be
required, as the desired  domain gets further and further from simple
finite set theory and elementary number theory.

. SKIP TO COLUMN 1; SSSEC(AM as a Book)

.QQ

Walking home  along a deserted street  late at night, the  reader may
imagine himself to feel in the small of his back a cold, hard object;
and to  hear  the words  spoken  behind him,  `Easy  now. This  is  a
stick-up.    Hand over  your  money.' What  does  the  reader do?  He
attempts to generate the utterance. He says to himself, now if I were
standing behind  someone  holding a  cold, hard  object against  his
back, what  would make  me say  that? What  would I  mean by  it? The
reader is advised that  he can only arrive  at the deep structure  of
this  book, and  through  the  deep structure  the  semantics, if  he
attempts  to generate  the book  for himself.  The author  wishes him
luck.

-- Linderholm

.ESS

. TURN ON "{}";

Each chapter is of roughly equal importance, which explains the huge variation
in length.
Start looking over Chapter {[2]EXAM1} right away: it contains
a detailed example of what AM does. 
Since you're reading this sentence now, we'll assume that
you want a preview of
what's to come in the rest of this document.

Chapter 3 covers the top-level control structure of the system, which is
based around the notion of an `agenda' of tasks to perform.
In Chapter 4 the low-level control structure is revealed: AM is really
guided by a mass of heuristic rules of varying generality.
Chapter 5 contains more than you want to know about the representation
of knowledge in AM. 
The diagram showing some of AM's starting concepts
(page {[3]TREECON}) is worth a look, even out of context.

Most of the results of the project are presented in Chapter 6. In addition to
simply `running' AM, several experiments have been conducted with it.
It's awkward to evaluate AM, and therefore Chapter 7 is quite long and detailed.

The appendices provide material which supplements the text. 
Appendix {[2]ALLCON} contains a description of a few of the initial concepts,
some examples of how they were coded into Lisp, and a partial list of the
concepts AM defined and investigated along the way.
Appendix {[2]ALLHEU} exhibits all  {[3]TRULES} heuristics that AM is
explicitly provided with.
Appendix {[2]TRACES} contains traces of AM in action.

This book  -- and its  readers --  must come to  grips with a  very
interdisciplinary  problem.   For the reader  whose background  is in
Artificial  Intelligence,  most  of  the  system's  actions   --  the
"mathematics" it does  -- may seem inherently  uninteresting. For the
mathematician,  the  word "LISP"  signifies  nothing beyond  a speech
impediment  (to Artificial  Intelligence  types  it also  connotes  a
programming impediment). As a result, there is a good bit
of definition and explanation, and the reader's indulgence is entreated.